home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 09 - 1993 / 09.05 May 93 / Programmers' Challenge / TxtCount.c
Encoding:
Text File  |  1993-03-10  |  5.6 KB  |  182 lines  |  [TEXT/KAHL]
  1.  
  2. //******************************************
  3. //    Unique word count by Ronald M. Nepsund
  4.                                     //    please do not publish my address and phone number
  5.                                     //    Ronald M. Nepsund
  6.                                     //    19229 Nordhoff St. #35
  7.                                     //    Northridge,Ca    91324
  8.                                     //    Work phone (818) 701-5051
  9.                                     //    Home phone (818) 885-0810
  10. //The original text is uppercased with all non alphabetic characters
  11. //turned to zero.
  12. //The list of unique words works as follows
  13. //The word is used to to index into a 1024 entry hash table.
  14. //The hash table contains pointers to the beginning of a linked
  15. //list of word entries.  Each word entry holds the length of
  16. //the word and a pointer to the first occurance of the word
  17. //in the original text.  The linked list is ordered first by the
  18. //length of the words and secondly alphabetically
  19.  
  20. #define    kHashMask    0x003FF
  21. #define    kHashSize    0x00400
  22.  
  23. typedef    struct    tNode{
  24.         short            length;
  25.         Ptr                wordPtr;
  26.         struct    tNode    *nextNode;
  27.     } WordTableRec,*WordTablePtr;
  28.  
  29.  
  30. //compare two strings
  31. short stringCmp(register short length,
  32.                 register char *pnt1, register char *pnt2)
  33. {
  34.     while (--length > 0 && *pnt1==*pnt2)    {
  35.         pnt1++; pnt2++;
  36.     }
  37.     return *pnt1-*pnt2;
  38. }
  39.  
  40. unsigned short CountUniqueWords(Ptr    textPtr,unsigned short byteCount)
  41. {
  42.     Ptr                endPnt,wordStartPtr;
  43.     register char    *charPnt;
  44.     register long    hash;
  45.     long            count;
  46.     register short    wordLength;
  47.     unsigned short    totalWords = 0;
  48.     short            i,cmp;
  49.     WordTablePtr    *hashTable;
  50.     WordTablePtr    wordTable;
  51.     register WordTablePtr    linkPtr;
  52.     WordTablePtr    last,wordTableEntry;
  53.     char            charTypeTable[256];
  54.     long            *zeroTblPtr;
  55.     //total possable number of words = 16556
  56.     //assuming a maximum size buffer of text
  57.     //I will use a hash table size of 1024
  58.     
  59.     count = 4L * kHashSize;
  60.     hashTable = (WordTablePtr *)NewPtrClear(count);    //array of (NULL)Ptr's
  61.     if (hashTable == 0L)
  62.         while (TRUE)
  63.             SysBeep(10);    //not enough memory
  64.     
  65.     count = 16556L * sizeof(WordTableRec);
  66.     wordTable = (WordTablePtr)NewPtr(count);
  67.     
  68.     if (wordTable == 0L)
  69.         while (TRUE)
  70.             SysBeep(10);    //not enough memory
  71.     //zero out the 'charTypeTable'
  72.     zeroTblPtr = (long *)&charTypeTable;
  73.     for (i=0; i<64; i++)
  74.         *zeroTblPtr++ = 0;
  75.  
  76.     //init lookup table used for uppercasing and identifying non letter characters
  77.     for (i=0;i<26; i++)
  78.         charTypeTable[i+(Byte)'A'] =
  79.         charTypeTable[i+(Byte)'a'] = (char)(i+((Byte)'A'));
  80.     
  81.     totalWords = 0;
  82.     charPnt = textPtr;
  83.     endPnt = textPtr + byteCount;
  84.     while (charPnt < endPnt)    {
  85.         //skip spaces
  86.         while (charPnt < endPnt && charTypeTable[*charPnt] == 0)
  87.             charPnt++;
  88.         wordStartPtr = charPnt;    //pointer to begining of new word
  89.         hash    =    0;
  90.         if (endPnt-charPnt > 255)    {    //at least 255 characters left
  91.             //advance to the end of the word
  92.             //we can assume that a word is <=255 characters long
  93.             //uppercasing the text
  94.             //and doing a hash function
  95.             while (*charPnt = charTypeTable[*charPnt])
  96.                 hash = (hash << 4)  + *charPnt++ - 'A' + (hash >> 10);
  97.                 
  98.         }    else    {
  99.             while (charPnt < endPnt && (*charPnt = charTypeTable[*charPnt]))
  100.                 hash = (hash << 4) + *charPnt++ - 'A' + (hash >> 10);
  101.         }
  102.         wordLength = charPnt-wordStartPtr;
  103.  
  104.         hash &=  kHashMask;
  105.         //hash &=  0x3FFF;
  106.         linkPtr = (WordTablePtr)hashTable[hash];
  107.             
  108.         last = NULL;
  109.         if (linkPtr==NULL)    {    //this hash entry has not been used yet
  110.             wordTableEntry = &wordTable[totalWords++];
  111.             hashTable[hash] = wordTableEntry;
  112.             wordTableEntry->length   = wordLength;
  113.             wordTableEntry->wordPtr  = wordStartPtr;
  114.             wordTableEntry->nextNode = 0;
  115.         }    else    {
  116.             //the entries are ordered by word length
  117.             //find the first entry that is as long or longer
  118.             while (linkPtr != NULL && linkPtr->length < wordLength)    {
  119.                 last = linkPtr;
  120.                 linkPtr = linkPtr->nextNode;
  121.             }
  122.             if (linkPtr == NULL)    {    //no other entries as long as this one
  123.                 wordTableEntry = &wordTable[totalWords++];
  124.                 if (last == NULL)
  125.                     hashTable[hash] = wordTableEntry;
  126.                 else
  127.                     last->nextNode = wordTableEntry;
  128.                 wordTableEntry->length = wordLength;
  129.                 wordTableEntry->wordPtr= wordStartPtr;
  130.                 wordTableEntry->nextNode= NULL;
  131.             }    else
  132.                 if     (linkPtr->length > wordLength){
  133.                     //insert betean 'last' and 'linkPtr'
  134.                     wordTableEntry = &wordTable[totalWords++];
  135.                     if (last == NULL)    {
  136.                             wordTableEntry->nextNode = hashTable[hash];
  137.                             hashTable[hash] = wordTableEntry;
  138.                     }    else    {
  139.                             wordTableEntry->nextNode = last->nextNode;
  140.                             last->nextNode = wordTableEntry;
  141.                     }
  142.                     wordTableEntry->length = wordLength;
  143.                     wordTableEntry->wordPtr= wordStartPtr;
  144.                 } else    {    //check entries with same word lengths
  145.                     while (linkPtr != NULL && linkPtr->length == wordLength &&
  146.                             (cmp = stringCmp(wordLength,wordStartPtr,linkPtr->wordPtr)) <0)    {
  147.                         last = linkPtr;
  148.                         linkPtr = linkPtr->nextNode;
  149.                     }
  150.                     if (linkPtr == NULL)    {    //end of list and no match
  151.                         wordTableEntry = &wordTable[totalWords++];
  152.                         if (last == NULL)
  153.                             hashTable[hash] = wordTableEntry;
  154.                             else
  155.                             last->nextNode = wordTableEntry;
  156.                         wordTableEntry->length = wordLength;
  157.                         wordTableEntry->wordPtr= wordStartPtr;
  158.                         wordTableEntry->nextNode= 0;
  159.                     }    else
  160.                         if (linkPtr->length > wordLength || cmp>0)    {
  161.                             //insert word entry here
  162.                             wordTableEntry = &wordTable[totalWords++];
  163.                             if (last == NULL)    {    //hash table to point here
  164.                                 wordTableEntry->nextNode = hashTable[hash];
  165.                                 hashTable[hash] = wordTableEntry;
  166.                             }    else    {
  167.                                 wordTableEntry->nextNode= last->nextNode;
  168.                                 last->nextNode = wordTableEntry;
  169.                             }
  170.                             wordTableEntry->length  = wordLength;
  171.                             wordTableEntry->wordPtr = wordStartPtr;
  172.                         }
  173.                 }
  174.         }
  175.     }
  176.     
  177.     DisposePtr((Ptr)hashTable);
  178.     DisposePtr((Ptr)wordTable);
  179.     return totalWords;
  180. }
  181.  
  182.